Big Omega（大Ω记号，Ω）是算法与计算复杂度分析中的一种渐近下界表示法：若函数 \(f(n)\) 的增长速度在足够大的 \(n\) 上至少像 \(g(n)\) 那样快，则写作
\[ f(n) = \Omega(g(n)). \]
常用来表达“最少需要这么多时间/空间”。（在数学里 Ω 也可能有其他含义，但计算机科学中最常见的是“渐近下界”。）
/b ome/
For comparison-based sorting, the time complexity is Ω(n log n).
对于基于比较的排序算法，时间复杂度下界是 Ω(n log n)。
Although the average case may be faster, the algorithm still has an Ω(n) worst-case running time on adversarial inputs.
尽管平均情况可能更快，但在对抗性输入下，该算法的最坏运行时间仍然有 Ω(n) 的下界。
“Big Omega”里的 Omega（Ω）来自希腊字母表的最后一个字母“ω/Ω”。在渐近符号体系中，它与 Big O（O）、Big Theta（Θ）并列，形成一套用希腊字母表示增长（Landau 记号）的传统；其中 Ω被约定用来表示“从下方界定”的增长速度（下界）。
Select Language